
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<!--
Design by Farzon Lotfi
-->
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>LCC 3403 HashMaps Group</title>
<meta name="description" content="Guides to HashMaps" />
<meta name="keywords" content="Hashmaps, tutorials, lectures" />
<meta name="author" content="Farzon, Lotfi" />

<link href="style.css" rel="stylesheet" type="text/css" />
<!-- Definitely use these for development -->
<script src="./js/jquery-1.7.2.min.js"></script>
<script src="./js/jquery-ui-1.8.20.custom.min.js"></script>

<!-- This of course is required. The full version (not .min) is also included in the js directory -->
<script src="./js/jquery.coda-slider-3.0.min.js"></script>
 <script>
    $(function(){

      /* Here is the slider using default settings */
      $('#slider-id').codaSlider();
      $('#slider-id0').codaSlider();
      
      document.getElementById('six_essentials').style.display = 'none';
      document.getElementById('coll').style.display       = 'none';
      document.getElementById('disad').style.display      = 'none';
      document.getElementById('advantages').style.display = 'none';
      
      /* If you want to adjust the settings, you set an option
         as follows:

          $('#slider-id').codaSlider({
            autoSlide:true,
            autoHeight:false
          });
      */
    });
</script>
</head>
<script language="javascript" type="text/javascript">
function showHide(shID) {
  if (document.getElementById(shID)) {
    if (document.getElementById(shID+'-show').style.display != 'none') {
      document.getElementById(shID+'-show').style.display = 'none';
      document.getElementById(shID).style.display = 'block';
    }
    else {
      document.getElementById(shID+'-show').style.display = 'inline';
      document.getElementById(shID).style.display = 'none';
    }
  }
}
</script>
<body>
<div class="wrapper row1">
  <header id="header" class="clear">
    <hgroup>
      <h1><a href="#">HashMaps</a></h1>
      <h2>The Refresher Course</h2>
    </hgroup>
    <nav>
      <ul>
        <li><a href="notes.html">Notes</a></li>
        <li><a href="videos.html">Web Series</a></li>
        <li><a href="demo.html">Demo</a></li>
        <li><a href="questions.html">Interview Questions</a></li>
        <li class="last"><a href="tips.html">Interview Tips</a></li>
      </ul>
    </nav>
  </header>
</div>
<!-- content -->
<div class="wrapper row2">
  <div id="container" class="clear">
    <!-- Slider -->
    <section id="slider" class="clear">
      <figure><iframe style="float:right" width="600" height="300" src="http://www.youtube.com/embed/SwYuukKsdJ0" frameborder="0" allowfullscreen></iframe>
        <figcaption>
          <h2>Hash Maps Review</h2>
           <p> Hash Maps are a Data Structure that are frequently used in Computer Science </p>
           <footer class="more0"><a href="#" id="six_essentials-show" class="showLink" onclick="showHide('six_essentials');return false;">Read More &raquo;</a></footer>
        </figcaption>
      </figure>
    </section>
    <div id="six_essentials" class="more">
    <div class="coda-slider"  id="slider-id">
      <div>
        <h2 class="title">Key</h2>
        <p>Keys are unique numbers that are paired with the value when hashing, it is necessary that every key be unique because if there are multiple of the same value you want to be able to maintain the multiple copies instead of overwriting the single value each time you try to add a new key and value pair.</p>
      </div>
      <div>
        <h2 class="title">Value</h2>
        <p>Values are the important parts of data being stored in your hash maps, examples include names and addresses, however, you will still need a unique key for each one in the event that there are duplicates.</p>
      </div>
      <div>
        <h2 class="title">Hashing Function</h2>
        <p>This is where the magic happens, the hashing function is what determines what key/value pairs go where.  A hashing function can be written a number of ways but the key to writing one is to have an equal distribution of numbers across a range.  You need this distribution to prevent bunching up of numbers which in turn will create a large amount of collisions.  For example, Java uses the reference value of the object you are hashing in their hashing function.  A common, but sloppy approach to writing a basic hashing function is to just add up the ascii values of each character in the name if the value you are hashing is a string.</p>
      </div>
      <div>
        <h2 class="title">Compression Function</h2>
        <p>After computing the hash of the value with the hashing function you need to stick it in the hash table.  However, your map is only a certain size, say 11 elements.  If you get a hash value of 110 then where are you going to stick it? This is where the compression function comes into play.  It basically takes the size of the array and your hash value and mods them together to find the slot to stick the key/value pair in.</p>
      </div>
      <div>
        <h2 class="title">Array</h2>
        <p>The array is where we actually store the elements, depending on which type of collision management we are using each element in the array could also be a linked list.</p>
      </div>
      <div>
        <h2 class="title">Load Factor</h2>
        <p>A ratio of elements to used to determine when resizing of the hash table is necessary.</p>
      </div>
      <div>
        <h2 class="title">Resizing</h2>
        <p>When the load factor that is set for the hash map is reached it is time to resize your array.  In order to resize you must first create a larger array than the previous one, usually you will do double the size of the previous array and add 1.  Once you have the new empty array you will take each element from the previous array and rehash it into the new array.</p>
      </div>
    </div>
    <p><a href="#" id="six_essentials-hide" class="hideLink" onclick="showHide('six_essentials');return false;">Hide this content.</a></p>
     </div>
    <!-- main content 2-->
    <div id="homepage">
      <!-- services area -->
      <section id="services" class="clear">
        <!-- article 1 -->
        <article class="one_third">
          <h2>HashMap Advantages</h2>
          <img src="webImages/upvote.png" alt=""/>
          <p>The main advantage of hash maps is speed. This advantage is noticable when the data set is large. Hash tables are particularly efficient when you do not need to resize, so that the buckets can be allocated once with the optimum size.</p>
          <footer class="more0"><a href="#" id="advantages-show" class="showLink" onclick="showHide('advantages');return false;">Read More &raquo;</a></footer>
        </article>
        <!-- article 2 -->
        <article class="one_third">
          <h2>HashMap Disadvantages</h2>
          <img src="webImages/downvote.png" alt=""/>
          <p> The cost of a good hashing function can cost more than the lookup algorithm for a sequential list or search tree. Thus hash tables are not effective on small data sets. the cost can be mitigated by storing the hash value together with the key. This reduces computation time but will increase storage space.</p>
          <footer class="more0"><a href="#" id="disad-show" class="showLink" onclick="showHide('disad');return false;">Read More &raquo;</a></footer>
        </article>
        <!-- article 3 -->
        <article class="one_third lastbox">
          <h2>Collision Management</h2>
          <img src="webImages/collision.png" alt=""/>
          <p>When inserting elements into the hash map you will sometimes find that when you go to insert the element there is already an element in the slot, this is known as a collision, in order to deal with this collision we must perform some collision management.  We will be discussing two types of collision management, linear probing and external chaining.</p>
          <footer class="more0"><a href="#" id="coll-show" class="showLink" onclick="showHide('coll');return false;">Read More &raquo;</a></footer>
        </article>
      </section>
      <!-- / services area -->
      <!-- ########################################################################################## -->
      <!-- ########################################################################################## -->
      <!-- ########################################################################################## -->
      <!-- ########################################################################################## -->

    </div>
    <!-- / content body -->
     <div id="advantages" class="more">
      <h2>Advantages</h2>
      <p>The main advantage of hash maps is speed. This advantage is noticable when the data set is large. Hash tables are particularly efficient when you do not need to resize, so that the buckets can be allocated once with the optimum size. On average a hash map will provide an O(1) Insertion, Lookup, and Deletion.  What this boils down to is that you can find, add and delete your data very quickly.</p>
      <p><a href="#" id="advantages-hide" class="hideLink" onclick="showHide('advantages');return false;">Hide this content.</a></p>
    </div>
    <div id="disad" class="more">
     <h2>Disadvantages</h2>
      <p>The cost of a good hashing function can cost more than the lookup algorithm for a sequential list or search tree. Thus hash tables are not effective on small data sets. the cost can be mitigated by storing the hash value together with the key. This reduces computation time but will increase storage space. As stated above the average run time is O(1) time however in order to keep a run time this fast you must deal with an extremely large amount of space.  Depending on your load factor your hash map could either have a lot of empty space or very little when you try to add lots of elements.  In order to prevent collisions you must have a reasonable load factor, most of the time this is around 75%.  Collisions are a very real problem and there are various ways of dealing with them but we will go into detail about them later.</p>
      <p><a href="#" id="disad-hide" class="hideLink" onclick="showHide('disad');return false;">Hide this content.</a></p>
    </div>
    
    <div id="coll" class="more">
     <h2>Collisions</h2>
      <div class="coda-slider"  id="slider-id0">
        
        <div>
        <h2 class="title">Intro</h2>
        <p>When inserting elements into the hash map you will sometimes find that when you go to insert the element there is already an element in the slot, this is known as a collision, in order to deal with this collision we must perform some collision management.  We will be discussing two types of collision management, linear probing and external chaining.  </p>
        </div>
        
        <div>
        <h2 class="title">External Chaining</h2>
        <p>With external chaining each element in the array is actually a linked list.  This means that when you have a collision all that is necessary is to insert the new value to the front of the linked list.  Since you are expanding the hash map both vertically and horizontally resizing the hash map may take a lot longer than expected, depending on the number of elements in each linked list since each of these elements must be rehashed.  </p>
        </div>
        
        <div>
        <h2 class="title">Linear Probing</h2>
        <p>The first of the two types of collision management we will discuss, linear probing says that whenever you encounter a collision you will add the element you were going to add in the next available spot.  When removing and searching for an element you must continue searching until you arrive back at the initial spot or you find an empty spot.  When you go to remove an element you must look to the next elements in the array and if they match the hash of the element being removed you must reinsert them into the hash, this is done to prevent the possibility of not being able to find an element that is actually in the hash map.The point at which linear probing begins to not work so well is when you have a very high load factor. With a high load factor you will have a lot of collisions and not so much empty space so when you have a collision the cost of dealing with them is very high, on the other hand in order for linear probing to work well you must have a good amount of space, which can become a problem if space is limited on the system.</p>
        </div>
      </div>
      <p><a href="#" id="coll-hide" class="hideLink" onclick="showHide('coll');return false;">Hide this content.</a></p>
    </div>
     
  </div>
</div>
<!-- Footer -->
<div class="wrapper row3">
  <footer id="footer" class="clear">
    <p class="fl_left">Copyright &copy; 2012 - All Rights Reserved </p>
  </footer>
</div>
 <!-- <script type="application/dart" src="web/start.dart"></script>
 <script src="https://dart.googlecode.com/svn/branches/bleeding_edge/dart/client/dart.js"></script>  -->
</body>

</html>
